// 数字的个数（Amount of Degrees，牛客 NC50516）
// 陈锋
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int N, M, K, B, Ans;
//从右往左构造，每次隔一段距离加一个1
// c1:1的个数； cur: 当前构造好的数字； pb:B的幂
void dfs(int c1, int cur, int pb) {
  if (c1 == K) {
    if (cur >= N) Ans++;
    return;
  }
  // next_pb下一个ai = 1对应的B^i
  for (LL next_pb = c1 ? pb * B : 1; cur + next_pb <= M; next_pb *= B)
    dfs(c1 + 1, cur + next_pb, next_pb);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> N >> M >> K >> B;
  dfs(0, 0, 0);
  cout << Ans << endl;
  return 0;
}
/*
  本题说明了DP和搜索问题的紧密联系
*/
// 46279129  Amount of Degrees  答案正确  100  4  376  561  C++  2020-12-26 21:04:56